#ifndef _CRT_EVRBTREE_H_
#define _CRT_EVRBTREE_H_

#include <crt_util.h>

/*
This rbtree, I copy nginx-rbtree, I rename it
If you use the Linux kernel tree, you cannot handle the same key
The TKS, nginx authors
*/

typedef long ev_rbtree_key_t;
typedef long ev_rbtree_key_int_t;
typedef int ev_int_t;
typedef struct ev_rbtree_node_s ev_rbtree_node_t;
typedef struct ev_rbtree_s ev_rbtree_t;

struct ev_rbtree_node_s {
    ev_rbtree_key_t key;
    ev_rbtree_node_t* left;
    ev_rbtree_node_t* right;
    ev_rbtree_node_t* parent;
    u_char color;
    u_char data;
};

typedef void (*ex_rbtree_insert_pt)(ev_rbtree_node_t* root, ev_rbtree_node_t* node, ev_rbtree_node_t* sentinel);

struct ev_rbtree_s {
    ev_rbtree_node_t* root;
    ev_rbtree_node_t* sentinel;
    ex_rbtree_insert_pt insert;
};

#define ev_rbtree_init(tree, s, i) \
    ev_rbtree_sentinel_init(s); \
    (tree)->root = s; \
    (tree)->sentinel = s; \
    (tree)->insert = i

#define ev_rbtree_data(node, type, link) (type*)((u_char*)(node)-offsetof(type, link))

ev_rbtree_node_t* ev_rbtree_min(ev_rbtree_node_t* node, ev_rbtree_node_t* sentinel);
void ev_rbtree_insert(ev_rbtree_t* tree, ev_rbtree_node_t* node);
void ev_rbtree_delete(ev_rbtree_t* tree, ev_rbtree_node_t* node);
void ev_rbtree_insert_value(ev_rbtree_node_t* root, ev_rbtree_node_t* node, ev_rbtree_node_t* sentinel);
void ev_rbtree_insert_timer_value(ev_rbtree_node_t* root, ev_rbtree_node_t* node, ev_rbtree_node_t* sentinel);
ev_rbtree_node_t* ev_rbtree_next(ev_rbtree_t* tree, ev_rbtree_node_t* node);

#define ev_rbt_red(node)              ((node)->color = 1)
#define ev_rbt_black(node)            ((node)->color = 0)
#define ev_rbt_is_red(node)           ((node)->color)
#define ev_rbt_is_black(node)         (!ev_rbt_is_red(node))
#define ev_rbt_copy_color(n1, n2)     (n1->color = n2->color)
#define ev_rbtree_sentinel_init(node) ev_rbt_black(node)

#endif /* _EV_RBTREE_H_ */
